package leetcode.shuangpoint;

import java.util.ArrayList;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回dictionary 中最长的字符串，
 该字符串可以通过删除 s 中的某些字符得到。

 如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。


 输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
 输出："apple"

 输入：s = "abpcplea", dictionary = ["a","b","c"]
 输出："a"

 */
public class FindLongestWord524 {

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("abe");
        list.add("abc");

        String res = new FindLongestWord524().findLongestWord("abce", list);
        System.out.println("res: "+res);
    }

    public String findLongestWord(String s, List<String> dictionary) {
        SortedSet<String> set = new TreeSet<>();
        int len = Integer.MIN_VALUE;
        for (String s1 : dictionary) {
            if(isSubStr(s,s1)){//匹配上了
                if(s1.length()>=len){
                    len = s1.length();
                    set.add(s1);
                }
            }
        }

        for (String s1 : set) {//第一个达到长度的就是结果
            if(len == s1.length())
                return s1;
        }
        return "";
    }


    private  boolean isSubStr(String s,String t){
        int i=0;
        int j=0;

        while (i<s.length() && j<t.length()){
            if(s.charAt(i) == t.charAt(j)){
                i++;
                j++;
            }else {
                i++;
            }
        }
        return j==t.length();
    }
}